// 给你一个整数数组 nums，你可以对它进行一些操作。
// 每次操作中，选择任意一个 nums[i]，删除它并获得 nums[i] 的点数。
// 之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
// 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/delete-and-earn
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function (nums) {
  let maxVal = -Infinity
  for (const num of nums) {
    maxVal = Math.max(num, maxVal)
  }

  // 如果将相同的元素加在一起，然后将它们放入数组，对应下标位元素值
  // 那么就变成了打家劫舍的问题
  const sums = new Array(maxVal + 1).fill(0)
  for (const num of nums) {
    sums[num] += num
  }

  const dp = new Array(maxVal + 1)
  dp[0] = 0
  dp[1] = sums[1]
  for (let i = 2; i <= maxVal; i++) {
    dp[i] = Math.max(
      dp[i - 1],
      dp[i - 2] + sums[i]
    )
  }

  return dp[maxVal]

  // 1. 在 sums 中从 0 到 i 能拿到的最大值
  const helper = (i) => {
    if (i === 0) {
      return sums[0]
    }
    if (i === 1) {
      return Math.max(sums[0], sums[1])
    }

    // 3. i 依赖 i - 1 和 i - 2
    const p1 = helper(i - 1)
    const p2 = helper(i - 2) + sums[i]

    return Math.max(p1, p2)
  }
  // 2. i 从 0 到 maxVal
  const res = helper(maxVal)

  return res
}


console.log(
  deleteAndEarn([8, 10, 4, 9, 1, 3, 5, 9, 4, 10])
)














